package com.linyaonan.leetcode.easy._872;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 * <p>
 * <p>
 * <p>
 * 举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
 * <p>
 * 如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 * <p>
 * 如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 * <p>
 *  
 * <p>
 * 提示：
 * <p>
 * 给定的两颗树可能会有 1 到 100 个结点。
 *
 * @author: Lin
 * @date: 2020/1/12
 */
public class LeafSimilarTrees {
    List<Integer> list1;
    List<Integer> list2;

    /**
     * 深度有限遍历，使用后序遍历，拿到的叶子值就是从左向后
     * @param root1
     * @param root2
     * @return
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        list1 = new ArrayList<>();
        list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        if (list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return false;
            }
        }
        return true;
    }

    private void dfs(TreeNode node, List<Integer> save) {
        if (node != null) {
            dfs(node.left, save);
            dfs(node.right, save);
            if (node.left == null && node.right == null) {
                save.add(node.val);
            }
        }
    }

//    private boolean check(TreeNode node) {
//        if (node != null) {
//            if (node.left == null && node.right == null) {
//                Integer i = list.get(list.size() - 1);
//                if (node.val != i) {
//                    return
//                }
//            }
//            dfs(node.left);
//            dfs(node.right);
//        }
//    }

}
